{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make Costs of Paths Equal in a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #tree #array #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #树 #数组 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minIncrements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使二叉树所有路径值相等的最小代价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;表示一棵 <b>满二叉树</b>&nbsp;里面节点的数目，节点编号从 <code>1</code>&nbsp;到 <code>n</code>&nbsp;。根节点编号为 <code>1</code>&nbsp;，树中每个非叶子节点&nbsp;<code>i</code>&nbsp;都有两个孩子，分别是左孩子&nbsp;<code>2 * i</code>&nbsp;和右孩子&nbsp;<code>2 * i + 1</code>&nbsp;。</p>\n",
    "\n",
    "<p>树中每个节点都有一个值，用下标从<b>&nbsp;0</b>&nbsp;开始、长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>cost</code>&nbsp;表示，其中&nbsp;<code>cost[i]</code>&nbsp;是第&nbsp;<code>i + 1</code>&nbsp;个节点的值。每次操作，你可以将树中&nbsp;<strong>任意</strong>&nbsp;节点的值&nbsp;<strong>增加</strong>&nbsp;<code>1</code>&nbsp;。你可以执行操作 <strong>任意</strong> 次。</p>\n",
    "\n",
    "<p>你的目标是让根到每一个 <strong>叶子结点</strong>&nbsp;的路径值相等。请你返回 <strong>最少</strong>&nbsp;需要执行增加操作多少次。</p>\n",
    "\n",
    "<p><b>注意：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>满二叉树</strong>&nbsp;指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个节点，且所有叶子节点距离根节点距离相同。</li>\n",
    "\t<li><strong>路径值</strong> 指的是路径上所有节点的值之和。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/04/binaryytreeedrawio-4.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 7, cost = [1,5,2,2,3,3,1]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>我们执行以下的增加操作：\n",
    "- 将节点 4 的值增加一次。\n",
    "- 将节点 3 的值增加三次。\n",
    "- 将节点 7 的值增加两次。\n",
    "从根到叶子的每一条路径值都为 9 。\n",
    "总共增加次数为 1 + 3 + 2 = 6 。\n",
    "这是最小的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/04/binaryytreee2drawio.png\" style=\"width: 205px; height: 151px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, cost = [5,3,3]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>两条路径已经有相等的路径值，所以不需要执行任何增加操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>n + 1</code> 是&nbsp;<code>2</code>&nbsp;的幂</li>\n",
    "\t<li><code>cost.length == n</code></li>\n",
    "\t<li><code>1 &lt;= cost[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-costs-of-paths-equal-in-a-binary-tree](https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-costs-of-paths-equal-in-a-binary-tree](https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[1,5,2,2,3,3,1]', '3\\n[5,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, i):\n",
    "        if i * 2 > len(self.cost): # leaf\n",
    "            return self.cost[i - 1]\n",
    "        l, r =  self.dfs(i * 2), self.dfs(i * 2 + 1)\n",
    "        self.ans += abs(r - l)\n",
    "        return max(l,r) + self.cost[i - 1]\n",
    "\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        \n",
    "        self.cost = cost\n",
    "        self.dfs(1)\n",
    "        \n",
    "        return self.ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        tmp = n\n",
    "        level = 0\n",
    "        while tmp:\n",
    "            level += 1\n",
    "            tmp >>= 1\n",
    "        \n",
    "        pre_end = n - 1\n",
    "        res = 0\n",
    "        for i in range(level - 1, 0, -1):\n",
    "            node_cnt = 1 << i\n",
    "            for j in range(pre_end, pre_end - node_cnt, -2):\n",
    "                if cost[j] < cost[j - 1]:\n",
    "                    res += cost[j - 1] - cost[j]\n",
    "                    cost[j] = cost[j - 1]\n",
    "                else:\n",
    "                    res += cost[j] - cost[j - 1]\n",
    "                    cost[j - 1] = cost[j]\n",
    "                \n",
    "                cost[(j - 1) // 2] += cost[j]\n",
    "            \n",
    "            pre_end -= node_cnt\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n//2 - 1, -1, -1):\n",
    "            l, r = i * 2 + 1, i * 2 + 2\n",
    "            ans += max(cost[l], cost[r]) - min(cost[l], cost[r])\n",
    "            cost[l] = cost[r] = max(cost[l], cost[r])\n",
    "            cost[i] += cost[l]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        n = 2\n",
    "        while pow(2,n) - 1 != len(cost):\n",
    "            n += 1\n",
    "        \n",
    "        while n>1:\n",
    "            #自底向上统计\n",
    "            for i in range(pow(2,n-1)-1,pow(2,n)-2,2):\n",
    "                ans += abs(cost[i]-cost[i+1])\n",
    "                cost[i//2] += max(cost[i],cost[i+1])\n",
    "            \n",
    "            n -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        startIdx = n // 2\n",
    "        while startIdx != 0:\n",
    "            for curr in range(startIdx, startIdx * 2, 2):\n",
    "                ans += abs(cost[curr] - cost[curr + 1])\n",
    "                cost[curr // 2] += max(cost[curr], cost[curr + 1])\n",
    "            startIdx = startIdx // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(n//2,0,-1):#从底向上求解\n",
    "            l=cost[i*2-1]\n",
    "            r=cost[i*2]\n",
    "            res +=abs(l-r)\n",
    "            cost[i-1] +=max(l,r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    贪心\n",
    "    从某个根节点开始往任意一个叶子节点走，一定存在和多个叶子节点共用的部分和每个叶子节点分叉的部分，\n",
    "    而公共的部分值是相同的，要使得不同的子树路径和相同，最少的变化就是将每个分叉子树路径都等于这些子树\n",
    "    路径上的最大值。\n",
    "    '''\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        '''\n",
    "        这里节点序号从1开始，比较便于根据2 * i和2 * i + 1定位子节点，由于是满二叉树，最后一个\n",
    "        根节点的序号是n // 2\n",
    "        由于这个是从1开始的，那么对应cost的下标就需要再减去1\n",
    "        '''\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            res += abs(cost[2 * i - 1] - cost[2 * i])\n",
    "            '''\n",
    "            这里需要注意的是题目要求的是每一个叶子结点的距离，而不是某个根节点下所有叶子结点的距离之和，\n",
    "            所以再将两个叶子结点值相等后，只取之中之一累加到根节点的值上即可\n",
    "            '''\n",
    "            cost[i - 1] += max(cost[2 * i - 1], cost[2 * i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        # 模板：经典树形DP贪心\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            left = cost[i * 2 - 1]\n",
    "            right = cost[i * 2]\n",
    "            if left > right:\n",
    "                cost[i - 1] += left\n",
    "                ans += left - right\n",
    "            else:\n",
    "                cost[i - 1] += right\n",
    "                ans += right - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(n - 1, 0, -2):\n",
    "            maxx = max(cost[i], cost[i - 1])\n",
    "            dis = abs(cost[i] - cost[i - 1])\n",
    "            res += dis\n",
    "            cost[(i - 1) // 2] += maxx\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(n//2,0,-1):#从底向上求解\n",
    "            l=cost[i*2-1]\n",
    "            r=cost[i*2]\n",
    "            res +=l-r if l>r else r-l\n",
    "            cost[i-1] +=l if l>r else r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(n//2,0,-1):\n",
    "            ans+=abs(cost[2*i-1]-cost[2*i])\n",
    "            cost[i-1]+=max(cost[2*i-1],cost[2*i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            res += abs(cost[i * 2 - 1] - cost[i * 2])\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "#         path_max = [0] * n\n",
    "#         def getMaxPath(i):\n",
    "#             if (i + 1) * 2 < n:\n",
    "#                 path_max[i] = cost[i] + max(getMaxPath(i * 2 + 1), getMaxPath((i + 1) * 2))\n",
    "#             else:\n",
    "#                 path_max[i] = cost[i]\n",
    "#             return path_max[i]\n",
    "#         all_max = getMaxPath(0)\n",
    "#         ans = 0\n",
    "#         def getMinAdd(i, path_sum):\n",
    "#             nonlocal ans\n",
    "#             path_sum -= cost[i]\n",
    "#             left = i * 2 + 1\n",
    "#             right = (i + 1) * 2\n",
    "#             if right < n:\n",
    "#                 if path_max[left] == path_sum: \n",
    "#                     ans += path_sum - path_max[right]\n",
    "#                 else:\n",
    "#                     ans += path_sum - path_max[left]\n",
    "#                 getMinAdd(left, path_max[left])\n",
    "#                 getMinAdd(right, path_max[right])\n",
    "#         getMinAdd(0, all_max)\n",
    "#         return ans\n",
    "# class Solution:\n",
    "#     def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "#         ans = 0\n",
    "#         def getMaxPath(i):\n",
    "#             nonlocal ans\n",
    "#             if (i + 1) * 2 < n:\n",
    "#                 left = getMaxPath(i * 2 + 1)\n",
    "#                 right = getMaxPath((i + 1) * 2)\n",
    "#                 if left > right:\n",
    "#                     left, right = right, left\n",
    "#                 ans += right - left\n",
    "#                 return cost[i] + right\n",
    "#             else:\n",
    "#                 return cost[i]\n",
    "#         getMaxPath(0)\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n - 1, 0, -2):\n",
    "            left, right = cost[i - 1], cost[i]\n",
    "            if left > right:\n",
    "                left, right = right, left\n",
    "            ans += right - left\n",
    "            cost[i // 2 - 1] += right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            ans += abs(cost[i*2-1] - cost[i*2])\n",
    "            cost[i-1] += max(cost[i*2-1], cost[i*2])\n",
    "        return ans\n",
    "        # @cache\n",
    "        # def dfs(x):\n",
    "        #     if x > n - 1:\n",
    "        #         return 0\n",
    "        #     a, b = dfs(x * 2+1), dfs(x * 2 + 2)\n",
    "        #     nonlocal ans \n",
    "        #     ans += abs(a - b)\n",
    "        #     return cost[x] + max(a, b)\n",
    "        # dfs(0)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        #自底向上，每个叶子节点先和自己的兄弟节点统一开销，然后在依次像根节点逼近。\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "\n",
    "        res=0\n",
    "        for i in range(n//2,0,-1):\n",
    "            res+=abs(cost[i*2-1]-cost[i*2])\n",
    "            cost[i-1]+=max(cost[i*2-1],cost[i*2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            res += abs(cost[2 * i - 1] - cost[2 * i])\n",
    "            cost[i - 1] += max(cost[2 * i - 1], cost[2 * i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i, j in zip(range(n-1, -1, -2), range(n-2, -1, -2)):\n",
    "            if i < n//2:\n",
    "                cost[i] = cost[i] + max(cost[2*i+1], cost[2*i + 2])\n",
    "                cost[j] = cost[j] + max(cost[2*j+1], cost[2*j+2])\n",
    "            res = res + abs(cost[i] - cost[j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        dp=cost.copy()\n",
    "        for i in range(n-1,0,-1):\n",
    "            f=(i-1)//2\n",
    "            dp[f]=max(dp[f],cost[f]+dp[i])\n",
    "        res=0\n",
    "        for i in range(n-1,0,-1):\n",
    "            f=(i-1)//2\n",
    "            res+=dp[f]-cost[f]-dp[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n//2,0,-1):\n",
    "            ans += abs(cost[2*i-1]-cost[2*i])\n",
    "            cost[i-1] += max(cost[2*i-1],cost[2*i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        i = n - 1\n",
    "        while i > 0:\n",
    "            res += abs(cost[i] - cost[i-1])\n",
    "            cost[i//2-1] += max(cost[i], cost[i-1])\n",
    "            i -= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(n//2,0,-1):\n",
    "            ans+=abs(cost[2*i-1]-cost[2*i])\n",
    "            cost[i-1]+=max(cost[2*i-1],cost[2*i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(cost)\n",
    "        for i in range(n//2, 0, -1):\n",
    "            res += abs(cost[2 * i] - cost[2*i-1])\n",
    "            cost[i-1] += max(cost[2*i], cost[2*i-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2 - 1, -1, -1):\n",
    "            ans += abs(cost[i * 2 + 1] - cost[i * 2 + 2])\n",
    "            cost[i] += max(cost[i * 2 + 1], cost[i * 2 + 2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  # 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  # 两个子节点变成一样的\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  # 累加路径和\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "#         path_max = [0] * n\n",
    "#         def getMaxPath(i):\n",
    "#             if (i + 1) * 2 < n:\n",
    "#                 path_max[i] = cost[i] + max(getMaxPath(i * 2 + 1), getMaxPath((i + 1) * 2))\n",
    "#             else:\n",
    "#                 path_max[i] = cost[i]\n",
    "#             return path_max[i]\n",
    "#         all_max = getMaxPath(0)\n",
    "#         ans = 0\n",
    "#         def getMinAdd(i, path_sum):\n",
    "#             nonlocal ans\n",
    "#             path_sum -= cost[i]\n",
    "#             left = i * 2 + 1\n",
    "#             right = (i + 1) * 2\n",
    "#             if right < n:\n",
    "#                 if path_max[left] == path_sum: \n",
    "#                     ans += path_sum - path_max[right]\n",
    "#                 else:\n",
    "#                     ans += path_sum - path_max[left]\n",
    "#                 getMinAdd(left, path_max[left])\n",
    "#                 getMinAdd(right, path_max[right])\n",
    "#         getMinAdd(0, all_max)\n",
    "#         return ans\n",
    "# class Solution:\n",
    "#     def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "#         ans = 0\n",
    "#         def getMaxPath(i):\n",
    "#             nonlocal ans\n",
    "#             if (i + 1) * 2 < n:\n",
    "#                 left = getMaxPath(i * 2 + 1)\n",
    "#                 right = getMaxPath((i + 1) * 2)\n",
    "#                 if left > right:\n",
    "#                     left, right = right, left\n",
    "#                 ans += right - left\n",
    "#                 return cost[i] + right\n",
    "#             else:\n",
    "#                 return cost[i]\n",
    "#         getMaxPath(0)\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n - 1, 0, -2):\n",
    "            left, right = cost[i - 1], cost[i]\n",
    "            if left > right:\n",
    "                ans += left - right\n",
    "                cost[i // 2 - 1] += left\n",
    "            else:\n",
    "                ans += right - left\n",
    "                cost[i // 2 - 1] += right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ret=0\n",
    "        for i in range(n-1,0,-2):\n",
    "            x=max(cost[i],cost[i-1])\n",
    "            ret+=abs(cost[i-1]-cost[i])\n",
    "            cost[(i-1)//2]+=x\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])\n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n//2,0,-1):# 从最后一个非叶节点开始算\n",
    "            ans += abs(cost[2*i-1]-cost[2*i])# 两个子节点变成一样的\n",
    "            cost[i-1] += max(cost[2*i-1],cost[2*i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 2, 0, -1):  \n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])  \n",
    "            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2])  \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(n // 2, 0, -1):\n",
    "            res += abs(cost[i * 2] - cost[i * 2 - 1])\n",
    "            cost[i - 1] += max(cost[i * 2], cost[i * 2 - 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(cost,idx):\n",
    "            childl = idx*2+1\n",
    "            if childl >= len(cost):\n",
    "                return \n",
    "            childr = idx*2+2\n",
    "            dfs(cost,childl)\n",
    "            dfs(cost,childr)\n",
    "            c = cost[childl]\n",
    "            d = cost[childr]\n",
    "            cost[idx] += max(c,d)\n",
    "            self.ans += abs(c-d)\n",
    "\n",
    "        dfs(cost,0)\n",
    "        # print(cost)\n",
    "        return  self.ans\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        leaf = []\n",
    "        \n",
    "        def dfs(node, val):\n",
    "            left, right = node * 2, node * 2 + 1\n",
    "            \n",
    "            if left > n or right > n: \n",
    "                leaf.append(val)\n",
    "                return \n",
    "            \n",
    "            dfs(left, val + cost[left - 1])\n",
    "            dfs(right, val + cost[right - 1])\n",
    "        \n",
    "        dfs(1, cost[0])\n",
    "        target = max(leaf)\n",
    "            \n",
    "        res = 0\n",
    "        \n",
    "        def dfs(l, t):\n",
    "            nonlocal res\n",
    "            if len(l) == 1:\n",
    "                res += t - l[0]\n",
    "            else:\n",
    "                a = t - max(l)\n",
    "                res += a\n",
    "                n = len(l)\n",
    "                dfs(l[:n//2], t-a)\n",
    "                dfs(l[n//2:], t-a)\n",
    "        \n",
    "        dfs(leaf, target)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(cost,idx):\n",
    "            childl = idx*2+1\n",
    "            if childl >= len(cost):\n",
    "                return \n",
    "            childr = idx*2+2\n",
    "            dfs(cost,childl)\n",
    "            dfs(cost,childr)\n",
    "            c = cost[childl]\n",
    "            d = cost[childr]\n",
    "            cost[idx] += max(c,d)\n",
    "            self.ans += abs(c-d)\n",
    "\n",
    "        dfs(cost,0)\n",
    "        print(cost)\n",
    "        return  self.ans\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        def dfs1(i, val):\n",
    "            if i > n:\n",
    "                return\n",
    "            cost[i - 1] += val\n",
    "            dfs1(i << 1, cost[i - 1])\n",
    "            dfs1(i << 1 | 1, cost[i - 1])\n",
    "        dfs1(1, 0)\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs2(i):\n",
    "            nonlocal ans\n",
    "            if i * 2 >= n: return\n",
    "            dfs2(i << 1)\n",
    "            dfs2(i << 1 | 1)\n",
    "            ans += abs(cost[i * 2 - 1] - cost[i * 2])\n",
    "            cost[i - 1] = max(cost[i * 2 - 1], cost[i * 2])\n",
    "        dfs2(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        self.res = 0\n",
    "        def dp(l, r):\n",
    "            if l == r:\n",
    "                return\n",
    "            for k in range(l, r + 1, 2):\n",
    "                max_ = max(cost[k - 1], cost[k])\n",
    "                self.res += 2 * max_ - cost[k - 1] - cost[k]\n",
    "                cost[k // 2 - 1] += max_ \n",
    "\n",
    "            dp(l // 2, l - 1)\n",
    "\n",
    "\n",
    "        left = (n + 1) // 2\n",
    "        right = n\n",
    "\n",
    "        dp(left, right)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        exp = int(math.log(n + 1, 2))\n",
    "        self.res = 0\n",
    "        def dp(l, r):\n",
    "            if l == r:\n",
    "                return\n",
    "            for k in range(l, r + 1, 2):\n",
    "                max_ = max(cost[k - 1], cost[k])\n",
    "                self.res += 2 * max_ - cost[k - 1] - cost[k]\n",
    "                cost[k // 2 - 1] += max_ \n",
    "\n",
    "            dp(l // 2, l - 1)\n",
    "\n",
    "\n",
    "        left = 1 << (exp - 1)\n",
    "        right = (1 << exp) - 1\n",
    "\n",
    "        dp(left, right)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        def dp(node):\n",
    "            left = 2*node+1\n",
    "            right = 2*node+2\n",
    "            if right > n:\n",
    "                return cost[node]\n",
    "            l = dp(left)\n",
    "            r = dp(right)\n",
    "            self.ans += abs(l-r)\n",
    "            return max(l,r)+cost[node]\n",
    "        dp(0)\n",
    "        return self.ans \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if node * 2 > n:\n",
    "                return cost[node - 1]\n",
    "            l = dfs(node * 2)\n",
    "            r = dfs(node * 2 + 1)\n",
    "            self.res += max(l, r) - min(l, r)\n",
    "            return max(l, r) + cost[node - 1]\n",
    "        dfs(1)\n",
    "        return self.res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        self.res = 0\n",
    "        \n",
    "        def dfs(x):\n",
    "            # 以这个节点为起点，到达叶子节点的路径和\n",
    "            if 2*x+1>n:\n",
    "                return cost[x-1]\n",
    "            left,right = 2*x, 2*x+1\n",
    "            left_sum = dfs(left)\n",
    "            right_sum = dfs(right)\n",
    "            maxv = max(left_sum, right_sum)\n",
    "            diff = maxv - min(left_sum, right_sum)\n",
    "            self.res += diff\n",
    "            return cost[x-1] + maxv\n",
    "\n",
    "        dfs(1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        # 自底向上，先修改下面的节点值，保证同一个子树下的路径和相等\n",
    "        self.res = 0\n",
    "        \n",
    "        def dfs(x):\n",
    "            # 以这个节点为起点，到达叶子节点的路径和\n",
    "            if 2*x+1>n:\n",
    "                return cost[x-1]\n",
    "            left,right = 2*x, 2*x+1\n",
    "            left_sum = dfs(left)\n",
    "            right_sum = dfs(right)\n",
    "            maxv = max(left_sum, right_sum)\n",
    "            diff = maxv - min(left_sum, right_sum)\n",
    "            self.res += diff\n",
    "            return cost[x-1] + maxv\n",
    "\n",
    "        dfs(1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        def max_path_sum(node):\n",
    "            if node > n:\n",
    "                return 0\n",
    "            return cost[node - 1] + max(max_path_sum(node * 2), max_path_sum(node * 2 + 1))\n",
    "\n",
    "        max_path = max_path_sum(1)\n",
    "        ans = 0\n",
    "        cur_sum = 0\n",
    "        height = int(log(n, 2))\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            nonlocal cur_sum\n",
    "            cur_sum += cost[node - 1]\n",
    "            if node * 2 > n:\n",
    "                ans += max_path - cur_sum\n",
    "                cur_sum -= cost[node - 1]\n",
    "                return cur_sum + cost[node - 1]\n",
    "            max_sum = max(dfs(node * 2), dfs(node * 2 + 1))\n",
    "            ans -= max_path - max_sum\n",
    "            cur_sum -= cost[node - 1]\n",
    "            return max_sum\n",
    "\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        def max_path_sum(node):\n",
    "            if node > n:\n",
    "                return 0\n",
    "            return cost[node - 1] + max(max_path_sum(node * 2), max_path_sum(node * 2 + 1))\n",
    "\n",
    "        max_path = max_path_sum(1)\n",
    "        ans = 0\n",
    "        cur_sum = 0\n",
    "        height = int(log(n, 2))\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            nonlocal cur_sum\n",
    "            cur_sum += cost[node - 1]\n",
    "            if node * 2 > n:\n",
    "                ans += max_path - cur_sum\n",
    "                cur_sum -= cost[node - 1]\n",
    "                return cur_sum + cost[node - 1]\n",
    "            max_sum = max(dfs(node * 2), dfs(node * 2 + 1))\n",
    "            ans -= max_path - max_sum\n",
    "            cur_sum -= cost[node - 1]\n",
    "            return max_sum\n",
    "\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "#         path_max = [0] * n\n",
    "#         def getMaxPath(i):\n",
    "#             if (i + 1) * 2 < n:\n",
    "#                 path_max[i] = cost[i] + max(getMaxPath(i * 2 + 1), getMaxPath((i + 1) * 2))\n",
    "#             else:\n",
    "#                 path_max[i] = cost[i]\n",
    "#             return path_max[i]\n",
    "#         all_max = getMaxPath(0)\n",
    "#         ans = 0\n",
    "#         def getMinAdd(i, path_sum):\n",
    "#             nonlocal ans\n",
    "#             path_sum -= cost[i]\n",
    "#             left = i * 2 + 1\n",
    "#             right = (i + 1) * 2\n",
    "#             if right < n:\n",
    "#                 if path_max[left] == path_sum: \n",
    "#                     ans += path_sum - path_max[right]\n",
    "#                 else:\n",
    "#                     ans += path_sum - path_max[left]\n",
    "#                 getMinAdd(left, path_max[left])\n",
    "#                 getMinAdd(right, path_max[right])\n",
    "#         getMinAdd(0, all_max)\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        def getMaxPath(i):\n",
    "            nonlocal ans\n",
    "            if (i + 1) * 2 < n:\n",
    "                left = getMaxPath(i * 2 + 1)\n",
    "                right = getMaxPath((i + 1) * 2)\n",
    "                if left > right:\n",
    "                    ans += left - right\n",
    "                    return cost[i] + left\n",
    "                else:\n",
    "                    ans += right - left\n",
    "                    return cost[i] + right\n",
    "            else:\n",
    "                return cost[i]\n",
    "        getMaxPath(0)\n",
    "        return ans\n",
    "# class Solution:\n",
    "#     def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "#         ans = 0\n",
    "#         for i in range(n - 1, 0, -2):\n",
    "#             left, right = cost[i - 1], cost[i]\n",
    "#             if left > right:\n",
    "#                 ans += left - right\n",
    "#                 cost[i // 2 - 1] += left\n",
    "#             else:\n",
    "#                 ans += right - left\n",
    "#                 cost[i // 2 - 1] += right\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "#         path_max = [0] * n\n",
    "#         def getMaxPath(i):\n",
    "#             if (i + 1) * 2 < n:\n",
    "#                 path_max[i] = cost[i] + max(getMaxPath(i * 2 + 1), getMaxPath((i + 1) * 2))\n",
    "#             else:\n",
    "#                 path_max[i] = cost[i]\n",
    "#             return path_max[i]\n",
    "#         all_max = getMaxPath(0)\n",
    "#         ans = 0\n",
    "#         def getMinAdd(i, path_sum):\n",
    "#             nonlocal ans\n",
    "#             path_sum -= cost[i]\n",
    "#             left = i * 2 + 1\n",
    "#             right = (i + 1) * 2\n",
    "#             if right < n:\n",
    "#                 if path_max[left] == path_sum: \n",
    "#                     ans += path_sum - path_max[right]\n",
    "#                 else:\n",
    "#                     ans += path_sum - path_max[left]\n",
    "#                 getMinAdd(left, path_max[left])\n",
    "#                 getMinAdd(right, path_max[right])\n",
    "#         getMinAdd(0, all_max)\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        def getMaxPath(i):\n",
    "            nonlocal ans\n",
    "            if (i + 1) * 2 < n:\n",
    "                left = getMaxPath(i * 2 + 1)\n",
    "                right = getMaxPath((i + 1) * 2)\n",
    "                if left > right:\n",
    "                    left, right = right, left\n",
    "                ans += right - left\n",
    "                return cost[i] + right\n",
    "            else:\n",
    "                return cost[i]\n",
    "        getMaxPath(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        def f(i):\n",
    "            nonlocal ans\n",
    "            if i * 2 > n:\n",
    "                return cost[i-1]\n",
    "            left = f(2 * i)\n",
    "            right = f(2 * i + 1)\n",
    "            if left == right:\n",
    "                return left + cost[i-1]\n",
    "            elif left > right:\n",
    "                ans += left - right\n",
    "                return left + cost[i-1]\n",
    "            else: \n",
    "                ans += right - left\n",
    "                return right + cost[i-1]\n",
    "\n",
    "        f(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res=0\n",
    "        def dfs(idx):\n",
    "            nonlocal res\n",
    "            if idx>n:return 0\n",
    "            l=dfs(2*idx)\n",
    "            r=dfs(2*idx+1)\n",
    "            res +=abs(l-r)\n",
    "            return max(l,r)+cost[idx-1]\n",
    "        \n",
    "        dfs(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        res=0\n",
    "        def dfs(x):\n",
    "            nonlocal res\n",
    "            if x > n:\n",
    "                return 0\n",
    "            left = dfs(2*x)\n",
    "            right = dfs(2*x+1)\n",
    "            res+=abs(left-right)\n",
    "            return cost[x-1]+max(left,right)\n",
    "        dfs(1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        n = n\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        def fix(i):\n",
    "            nonlocal n,count\n",
    "            \n",
    "            if i > n:\n",
    "                return 0\n",
    "            \n",
    "            lmax = fix(2*i)\n",
    "            rmax = fix(2*i+1)\n",
    "\n",
    "            if lmax == rmax:\n",
    "                return cost[i-1] + lmax \n",
    "            else:\n",
    "                count+= abs(lmax - rmax)\n",
    "                return cost[i-1] + max(lmax,rmax)\n",
    "        \n",
    "        fix(1)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        # 因为每一条路径都相等，所以每一个节点为根的子树的所有路径和都相等，所以每一可子树的节点的路径和应该等于这个子树所有路径的最大值，其余应该变为最大值，\n",
    "        # i,2*i,2*i+1\n",
    "        def dp(cur):\n",
    "            nonlocal ans\n",
    "            if cur>n:return 0\n",
    "            left=dp(cur*2)\n",
    "            right=dp(cur*2+1)\n",
    "            ans+=max(left,right)-min(left,right)\n",
    "            return max(left,right)+cost[cur-1]\n",
    "        ans=0\n",
    "        dp(1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ret = 0\n",
    "        def dfs(node):\n",
    "            left = node << 1 | 1\n",
    "            right = (node + 1) << 1\n",
    "            if left >= n:\n",
    "                return cost[node]\n",
    "            left = dfs(left)\n",
    "            right = dfs(right)\n",
    "            if left < right:\n",
    "                left, right = right, left\n",
    "            nonlocal ret\n",
    "            ret += left - right\n",
    "            # print(node,left, right, left + cost[node])\n",
    "            return left + cost[node]\n",
    "        dfs(0)\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(node):\n",
    "            nonlocal cnt\n",
    "            if node > n:\n",
    "                return 0\n",
    "            l = dfs(2 * node)\n",
    "            r = dfs(2 * node + 1)\n",
    "            cnt += abs(l - r)\n",
    "            return max(l, r) + cost[node - 1]\n",
    "        max_val = dfs(1)\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            if x > n:\n",
    "                return 0\n",
    "            left = dfs( x * 2)\n",
    "            right = dfs( x * 2 + 1)\n",
    "            #print(f\"root = {x} left = {left} right = {right}\")\n",
    "            ans += abs(left - right)\n",
    "            return max(left, right) + cost[x-1]\n",
    "        \n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if node>n:\n",
    "                return 0\n",
    "            left=dfs(node*2)\n",
    "            right=dfs(node*2+1)\n",
    "            ans+=abs(left-right)\n",
    "            return cost[node-1]+max(left,right)\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        #自底向上合并,贪心地选取操作次数\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if node>n:\n",
    "                return 0\n",
    "            left=dfs(node*2)\n",
    "            right=dfs(node*2+1)\n",
    "            ans+=abs(left-right)\n",
    "            return cost[node-1]+max(left,right)\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        def dfs(i):\n",
    "            # print(i)\n",
    "            if i*2 > n:\n",
    "                return (0, cost[i-1])\n",
    "            left = dfs(2*i)\n",
    "            right = dfs(2*i+1)\n",
    "            tmp = left[0] + right[0] + abs(left[1]-right[1])\n",
    "            return (tmp, max(left[1], right[1])+cost[i-1])\n",
    "        ans = dfs(1)[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(root:int)->int:\n",
    "            if root>n:\n",
    "                return 0 \n",
    "            l = dfs(root*2)\n",
    "            r = dfs(root*2+1)\n",
    "            nonlocal ans\n",
    "            ans += abs(l-r)\n",
    "            return  max(l,r)+cost[root-1]\n",
    "        dfs(1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "\n",
    "        self.ans = 0\n",
    "        self.mx = 0\n",
    "        def find_max(idx, now):\n",
    "            if idx > n:\n",
    "                self.mx = max(self.mx, now)\n",
    "                return 0\n",
    "\n",
    "            l = find_max(idx*2, now+cost[idx-1])\n",
    "            r = find_max(idx*2+1, now+cost[idx-1])\n",
    "\n",
    "            return l+r+cost[idx-1]\n",
    "\n",
    "        find_max(1,0)\n",
    "\n",
    "        self.ans = 0\n",
    "        def s_min(idx,now):\n",
    "            if idx > n:\n",
    "                return self.mx - now\n",
    "\n",
    "            l = s_min(idx*2, now+cost[idx-1])\n",
    "            r = s_min(idx*2+1,now+cost[idx-1] )\n",
    "\n",
    "\n",
    "            res = min(l,r)\n",
    "            self.ans += max(l,r) - min(l,r)\n",
    "\n",
    "            return res\n",
    "\n",
    "        s_min(1,0)\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\n",
    "        def dfs(i):\n",
    "            if i > n: return (0, 0)\n",
    "            l, tl = dfs(2 * i)\n",
    "            r, tr = dfs(2 * i + 1)\n",
    "            lr = l + r + abs(tl - tr)\n",
    "            t = max(tl, tr) + cost[i - 1]\n",
    "            return (lr, t)\n",
    "        t, c = dfs(1)\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\r\n",
    "        res = 0 \r\n",
    "        def dfs(x: int) -> int:\r\n",
    "            nonlocal res \r\n",
    "            if x * 2 > n:\r\n",
    "                #到达叶节点 \r\n",
    "                return cost[x - 1]\r\n",
    "            l = dfs(x * 2) \r\n",
    "            r = dfs(x * 2 + 1) \r\n",
    "            if l == r:\r\n",
    "                return l + cost[x - 1]\r\n",
    "            else:\r\n",
    "                res += abs(r - l)\r\n",
    "                return max(r, l) + cost[x - 1]\r\n",
    "        dfs(1)\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minIncrements(self, n: int, cost: List[int]) -> int:\r\n",
    "        res = 0 \r\n",
    "        def dfs(x: int) -> int:\r\n",
    "            nonlocal res \r\n",
    "            if x * 2 > n:\r\n",
    "                #到达叶节点 \r\n",
    "                return cost[x - 1]\r\n",
    "            l = dfs(x * 2) \r\n",
    "            r = dfs(x * 2 + 1) \r\n",
    "            res += abs(r - l)\r\n",
    "            return max(r, l) + cost[x - 1]\r\n",
    "        dfs(1)\r\n",
    "        return res "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
